%ATENCAO:
%PARA COMPILAR COM AS IMAGENS: pdflatex --shell-escape agg.tex
%
\documentclass[12pt]{article}

\usepackage{agg}

\usepackage{enumerate}

\usepackage[pdftex]{graphicx}
\usepackage{epstopdf}
\usepackage{subfigure}
\usepackage{url}
\usepackage{amsmath}
\usepackage{amssymb}


\usepackage[brazil]{babel}   
\usepackage[latin1]{inputenc}  

     
\sloppy

\title{Estudo do Problema da\\ \'Arvore Geradora M\'inima Generalizada com Coleta de Pr\^emio}

\author{Hugo Barbalho\inst{1}, Cinthya Fran\c ca \inst{1}}


\address{Instituto de Computa\c c\~ao -- Universidade Federal Fluminense
  (UFF)\\
  Niter\'oi -- RJ -- Brasil
  \email{hbarbalho@ic.uff.br,cfranca@ic.uff.br}
}

\begin{document} 

\maketitle

\begin{abstract}
This article propose a model of GRASP Local Search, where the definition of 
a Local Search neighborhood is partitioned into new smaller and disjoint local searches.
Computational experiments demonstrated that this technique contributed for the GRASP to 
find better solutions in a smaller computational time to the Prize Collecting Generalized Minimum Spanning Tree (PCGMST).
Another contribution of this work is the development of a separation algorithm to find dual limits to the problem.
Finally, the last contribuition was the creation of instances to the problem, which were used in the experiments of this work. 
  
%    This article propose a greed heuristic to build a initial solution for the Prize Collecting 
%Steiner Tree Problem (PCSTP) aiming to found better solutions than the ones already known in the 
%literature. Aplication of this problem can be found, as an instance, at network design in which 
%the place where the nodes are placed is relevant to the solution.
\end{abstract}
     
     
\begin{resumo} 
Neste trabalho, prop\~oe-se um modelo de busca local para o GRASP que particiona a defini\c c\~ao
de vizinhan\c ca de uma Busca Local em novas buscas locais menores e disjuntas. 
Experimentos computacionais mostraram que essa t\'ecnica 
contribuiu para que o GRASP encontrasse solu\c c\~oes melhores em um menor tempo computacional para o 
Problema da \'Arvore Geradora M\'inima Generalizada com Coleta de Pr\^emio. 
Outra contribui\c c\~ao deste trabalho \'e o desenvolvimento de um algoritmo de separa\c c\~ao para
encontrar limites duais para o problema. 
A terceira e \'ultima contribui\c c\~ao foi a cria\c c\~ao de 
inst\^ancias para o problema. Tais inst\^ancias foram utilizadas nos experimentos computacionais do trabalho.
%  Nesse trabalho \'e proposta um heur\'istica gulosa para constru\c c\~ao de uma solu\c c\~ao inicial 
%para o problema da \'arvore de Steiner com coleta de pr\^emio (Prize Collecting Steiner Tree problem - PCSTP), 
%que seja mais eficiente que as existentes na literatura. Aplica\c c\~oes desse problema podem ser encontradas, 
%por exemplo, em projetos de redes onde a localiza\c c\~ao dos n\'os tem influ\^encia na qualidade da solu\c c\~ao. 
\end{resumo}


\section{Introdu\c c\~ao}
  \input{introducao.tex}
O restante desse artigo est\'a organizado da seguinte maneira: 
Na se\c c\~ao 2, s\~ao propostas meta-heur\'isticas GRASP para o problema em quest\~ao.
Na se\c c\~ao 3, \'e apresentado o algoritmo de separa\c c\~ao seguido pelos cortes de cobertura.
Na se\c c\~ao 4, as inst\^ancias que foram geradas e usadas nos testes computacionais s\~ao introduzidas.
Na se\c c\~ao 5 s\~ao apresentados os resultados computacionais.
Finalmente, na se\c c\~ao 6, s\~ao feitas as considera\c c\~oes finais.
  
\section{Meta-heur\'istica GRASP} \label{sec:aplicacao}
  \input{secao3.tex}
  
\section{Relaxa\c c\~ao Linear e Corte de Cobertura} \label{sec:aplicacao}
  \input{secao4.tex}

\section{Gera\c c\~ao de Inst\^ancias}
  \input{secao5.tex}
    
\section{Resultados Computacionais}
  \input{secao6.tex}



\section{Conclus\~ao}
Desse trabalho podemos concluir que a divis\~ao da busca local em diferentes parti\c c\~oes tornou
a meta-heur\'istica mais robusta e eficiente, conseguindo encontrar solu\c c\~oes melhores para
o problema estudado. Mas ainda n\~ao sabemos se quanto mais parti\c c\~oes melhor, pois quanto maior
o n\'umero de parti\c c\~oes mais pr\'oximos estaremos da busca local baseada na estrat\'egia Primeira 
Melhora.

  Como pr\'oximo passo para esse trabalho, pretendemos aplicar tal m\'etodo de particionamento de busca local em problemas mais conhecidos
ou preferencialmente em uma classe espec\'ifica de problemas que use a mesma defini\c c\~ao de vizinhan\c ca.

  Quanto ao algoritmo de separa\c c\~ao, conseguimos encontrar solu\c c\~oes \'otimas provadas por GAP ou por 
integralidade da solu\c c\~ao, mas para algumas inst\^ancias o GAP ainda est\'a muito grande.

\bibliographystyle{sbc}
\bibliography{agg}

\end{document}
